home *** CD-ROM | disk | FTP | other *** search
/ FishMarket 1.0 / FishMarket v1.0.iso / fishies / 551-575 / disk_559 / rexxrmf / rexxrmflib.lzh / avl.structs.h < prev    next >
C/C++ Source or Header  |  1991-09-11  |  8KB  |  225 lines
  1.  
  2. /*:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::*
  3.  *::                                                                       ::*
  4.  *::  An implementaion of an AVL-Tree (balanced binary tree).              ::*
  5.  *::                                                                       ::*
  6.  *:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::*/
  7.  
  8. #define MAXKEYLEN     ((ULONG) 100)       /* maximum length of a key      */
  9.  
  10. #define MAXINDICES    ((ULONG) 8)         /* maximum number of indices    */
  11.                                           /* 0-5, 0=primary, 1-5=alt      */ 
  12.                                           /* 6=notused                    */
  13.                                           /* 7=deleted file blocks        */
  14.  
  15. #define DELETEINDEX   ((ULONG)  7)
  16.                                           
  17. #define MAXINDEXNUM   ((ULONG) 5)         /* max user index               */                                 
  18.  
  19.  
  20. /*** Key Data Structure ***/
  21.  
  22. struct Keydata 
  23. {
  24.    USHORT occurence; /* when duplicate keys allowed, specifies the  */
  25.                      /* occurence number of the node. Otherwise = 1 */
  26.                        
  27.    USHORT keylen;    /* length of the key data */
  28.    
  29.    char   *kdata;    /* pointer to key data */
  30.    
  31. };
  32.  
  33.  
  34.  
  35.  
  36. /***   Tree Node Structure  ***/
  37. /*  The binary tree is built  */  
  38. /*  using this structure      */
  39.  
  40. struct AvlNode
  41. {
  42.        struct AvlNode *llink;    /* points to the left child of this node   */
  43.        
  44.        struct AvlNode *rlink;    /* points to the right child of this node  */
  45.        
  46.        struct AvlNode *parent;   /* points to the parent of this node       */
  47.                                  /* follow up the tree, gives you the path  */
  48.                                
  49.        struct AvlNode *primary;  /* alternates point to their primary node  */
  50.  
  51.        struct AvlNode *alternatekeys[MAXINDICES]; /* primary points to alts */
  52.  
  53.        /* following fields used internally by AVL algorithm */
  54.        struct AvlNodeInfo {
  55.        
  56.               SHORT   balance;
  57.               USHORT  inxnum;
  58.               ULONG   rank;
  59.        } avi;
  60.        
  61.        
  62.        /* this part of the node stores data associated with the key */
  63.        struct AvlUserData
  64.        {
  65.               ULONG  recaddr;          /* This is assumed to be record   */
  66.                                        /* location in some external file */
  67.                                        /* for this key. This value gets  */
  68.                                        /* saved in the index file.       */
  69.                                        
  70.               ULONG  blklen;           /* block length of data           */
  71.  
  72.               struct Keydata *key;     /* pointer to the key value       */
  73.               
  74.               APTR   userdata1;        /* any data/pointer to data       */
  75.               APTR   userdata2;        /* any data/pointer to data       */
  76.                                        /* userdata1&2 are not saved in   */
  77.                                        /* the index file.                */
  78.               
  79.        } aud;
  80.        
  81.        
  82. } ;  /* End Structure AvlNode */
  83.  
  84.  
  85.  
  86.  
  87.  
  88. /***  Structure of the Index File  ***/
  89. /*                                   */
  90. /*  this is the index file header    */
  91. /*  It is loaded when the index file */
  92. /*  is opened. The AVL functions     */
  93. /*  return a pointer to this struct  */
  94. /*  for use in accessing the index   */
  95. /*  OPEN_RMF/MAKE_INDEX return a     */
  96. /*  pointer to this structure        */
  97. /*                                   */
  98. /*************************************/
  99.  
  100. struct IndexFile
  101. { 
  102.            
  103.    USHORT xid;                      /* identifies file as an index        */
  104.    ULONG  datestamp;                /* not used                           */
  105.    ULONG  numberofrecords;          /* number of keys in the index        */
  106.  
  107.    ULONG  compares;                 /* number of comparisons made during  */
  108.                                     /* search. (has no meaning at open)   */
  109.  
  110.    ULONG  height;                   /* the height of the binary tree      */
  111.                                     /* (has no meaning at open time)      */
  112.  
  113.    USHORT doserror;                 /* set to 0 if no errors occured      */
  114.  
  115.    USHORT rmferror;                 /* set to 0 if no errors occured      */
  116.                                     /* otherwise set to error code as     */
  117.                                     /* defined above.                     */
  118.  
  119.    ULONG prevpos;                   /* relative positions of previous key */
  120.                                     /* retrieved. (meaningless at open)   */
  121.  
  122.    ULONG rba_primary;               /* location where index entries begin.*/
  123.                                     /* should be valued. Tells where the  */
  124.                                     /* first index entry is located in    */
  125.                                     /* the index file.                    */
  126.  
  127.    ULONG fd_primary;                /* file handle for the index file     */
  128.                                     /* filled in at open time             */
  129.  
  130.    ULONG fd_data;                   /* file handle for the data  file     */
  131.                                     /* filled in at open time             */
  132.    UBYTE *indxname;                 /* points to filename of index file   */
  133.    UBYTE *filename;                 /* points to filename of data file    */
  134.    UBYTE *cmp1;
  135.    UBYTE *cmp2;
  136.    LONG  cmpl1;
  137.    LONG  cmpl2;
  138.    struct AvlNode *MRNode;          /* most recent AvlNode returned       */
  139.  
  140.    struct AvlNode *PrevSrchKey[MAXINDICES]; 
  141.    
  142.    struct AvlNode *SearchNode[MAXINDICES]; 
  143.    
  144.    struct AvlNode *IndexRoot[MAXINDICES];
  145.    
  146.    /* previous search type 'K','P','R', 'U'  */
  147.    UBYTE  prev_srch_type[MAXINDICES]; 
  148.    
  149.    UBYTE  dups;                     /* set to 1 if duplicates allowed     */
  150.                                     /* otherwise set to 0                 */
  151.            
  152. };
  153.  
  154.  
  155. /***   Structure of the Index File Entries   ***/
  156. /*     repeats for each primary key in file    */
  157.  
  158. struct DiskIndex 
  159. {
  160.  
  161.     struct DI_Info {
  162.     
  163.     ULONG  recaddr;             /* record location for this key     */
  164.                                 /* this is the location of a data   */
  165.                                 /* record in some external file.    */
  166.                                 
  167.     USHORT blklength;           /* length of record                 */                            
  168.     
  169.     UBYTE  rectype;             /* record type ??? dreaming I guess */
  170.     
  171.     UBYTE  recstatus;           /* record status = 'A'/'D'             */
  172.                                 /* 'A' active record                   */
  173.                                 /* a 'A' will have its keys (from      */
  174.                                 /* below) loaded in the corresponding  */
  175.                                 /* index. ie. if keylen[3] is non zero */
  176.                                 /* then keydata[3] is loaded in index  */
  177.                                 /* three.                              */
  178.                                 /* 'D' deleted record                  */
  179.                                 /* a 'D' record block automatically    */
  180.                                 /* gets loaded into the DELETEINDEX    */
  181.                                 /* regardless of the keylen info.      */
  182.  
  183.     USHORT keylen[MAXINDICES];  /* length of the key                   */
  184.     
  185.     } di_info;
  186.     
  187.     UBYTE  keydata[MAXKEYLEN*MAXINDICES]; /* the actual key value. */
  188.                                           /* keylen says how long, */
  189.                                           /* these are not NULL    */
  190.                                           /* terminated.           */
  191. } ;
  192.  
  193.  
  194.  
  195.  
  196. struct RecordHeader 
  197. {
  198.     SHORT blockid;                        /* not used */
  199.     LONG  blocklength;
  200.     SHORT dataoffset;
  201.     SHORT spare0;                         /* not used */
  202.     SHORT recordlength;
  203.     SHORT numberoffields;
  204.     ULONG datestamp;                      /* not used */
  205.     LONG  spare1;
  206.     SHORT spare2;
  207.     SHORT numaltindx;
  208. };
  209.  
  210. struct DataFileHeader 
  211. {
  212.     SHORT  fileid;                        /* not used */
  213.     ULONG  datestamp;                     /* not used */
  214.     LONG   spare0;
  215.     LONG   spare1;
  216.     SHORT  spare2;
  217.     SHORT  spare3;
  218.     SHORT  spare4;
  219. };
  220.  
  221. struct EOR_Trailer 
  222. {
  223.   UBYTE eor[4];
  224. };
  225.